import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[][] stones = {{0,0},{0,1},{1,0},{1,1}};
        System.out.println(s.removeStones(stones));
    }

    public int removeStones(int[][] stones) {
        /**
         * 移除最多的同行或同列石头
         * 解题思路：
         *  将所有行、列相同的坐标相同的节点合并到一个集合中
         *  但是目标元素是坐标形式，故我们采用二维转一维的思路进行操作 num = i * m + j*/
        // 1 预处理
        int m = stones.length;
        int n = stones[0].length;
        int sets = m;
        Map<Integer, Integer> map = new HashMap<>();
        // -求得已有x、y的最大值
        int col = 0;
        for(int[] e: stones) {
            if(e[1] > col) {
                col = e[1];
            }
        }
        col ++;
        // -对石头编号
        int num = 0;
        for(int[] e: stones) {
            map.put(e[0] * col + e[1], num++);
        }
        // - 初始化
        initialize(1000);

        // 2 遍历
        for(int i = 0; i < m-1; i++) {
            for(int j = i+1; j < m; j++) {
                int a = map.get(stones[i][0] * col + stones[i][1]);
                int b = map.get(stones[j][0] * col + stones[j][1]);
                // -只要x、y任意一个相同，且不在一个集合中，则合并
                if((stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) && !isSameSet(a,b)) {
                    union(a, b);
                    sets --;
                }
            }
        }

        // 3 计算返回值（每个集合元素个数-1 和）
        return m - sets;
    }

    // 并查集实现
    public static int MAX_N = 0;
    public static int[] father;
    public static int[] size;
    public static int[] stack;

    public static void initialize(int n) {
        /**
         * 初始化并查集*/
        // 1 分配空间
        MAX_N = n;
        father = new int[MAX_N];
        size = new int[MAX_N];
        stack = new int[MAX_N];

        // 2 初始化
        for(int i = 0; i < MAX_N; i++) {
            father[i] = i;
            size[i] = 1;
        }
    }

    public static int find(int a) {
        /**
         * 找到目标元素a所在集合的代表元素，并作扁平化处理*/
        int i = 0;
        while(a != father[a]) {
            stack[i++] = a;
            a = father[a];
        }
        while(i > 0) {
            father[stack[--i]] = a;
        }
        return a;
    }

    public static boolean isSameSet(int a, int b) {
        /**
         * 判断a、b元素是否处在同一集合中*/
        return find(a) == find(b);
    }

    public static void union(int a, int b) {
        /**
         * 合并a、b元素所在集合*/
        int fa = find(a);
        int fb = find(b);

        if(fa != fb) {
            if(size[fa] >= size[fb]) {
                size[fa] += size[fb];
                size[fb] = 1;
                father[fb] = fa;
            } else {
                size[fb] += size[fa];
                size[fa] = 1;
                father[fa] = fb;
            }
        }
    }
}
